package greedy;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/27 0:28
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 */
public class MaxProfit {

    /**
     * 正常思维：高买低卖
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int sum = 0;
        int flag = 0;
        int interest;
        for (int i = 0; i < prices.length - 1; i++) {
            interest = prices[i + 1] - prices[i];
            if (flag == 0 && interest >= 0) {
                //该点为增,低点，买
                sum -= prices[i];
                flag = 1;
            }
            if (flag == 1 && interest < 0) {
                //高点，卖
                sum += prices[i];
                flag = 0;
            }
        }
        if (flag == 1) {
            sum += prices[prices.length - 1];
        }
        return sum;
    }

    /**
     * 贪心算法 利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
     * 局部最优：收集每天的正利润，全局最优：求得最大利润。
     * @param prices
     * @return
     */
    public static int maxProfit1(int[] prices) {
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            int interest = prices[i] - prices[i - 1];
            sum += interest > 0 ? interest : 0;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        int i = maxProfit1(prices);
        System.out.println(i);
    }
}
